package com.zhanghp.class040;

/**
 * N皇后问题 <br/>
 * 测试链接 : https://leetcode.cn/problems/n-queens-ii/
 *
 * @author zhanghp
 * @since 2024/7/1 16:12
 */
public class Code02_NQueens {

    public int totalNQueens(int n) {
        if (n < 1) {
            return 0;
        }
        return f((1 << n) - 1, 0, 0, 0);
    }

    // 思路：利用对角线，列不能再一列
    // 用位运算处理
    // 分为，已存在的col的排列，left，right，根据行，来进行分别移动
    public static int f(int limit, int col, int left, int right) {
        if (limit == col) {
            return 1;
        }
        // 一共有多少有效的方法
        int ans = 0;
        /**
         * 总限制：col | left | right <br/>
         * 1 可放皇后，0不能放
         */
        int candidate = limit & ~(col | left | right);

        // 放置皇后的尝试！
        int place = 0;

        while (candidate != 0) {
            /**
             * 获取最右的1 ,{@link com.zhanghp.class031.Code01_PowerOfTwo}
             */
            // 0 0 1 1 1 0
            // 5 4 3 2 1 0
            // place :
            // 0 0 0 0 1 0
            // candidate :
            // 0 0 1 1 0 0
            // 5 4 3 2 1 0
            // place :
            // 0 0 0 1 0 0
            // candidate :
            // 0 0 1 0 0 0
            // 5 4 3 2 1 0
            // place :
            // 0 0 1 0 0 0
            // candidate :
            // 0 0 0 0 0 0
            // 5 4 3 2 1 0
            place = candidate & (-candidate);
            // 重置place（将刚提取的1，赋值为0）
            candidate ^= place;
            // 递归调
            ans += f(limit, (place | col), (place | left) << 1, (place | right) >> 1);
        }
        return ans;
    }

}
